package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/find-the-duplicate-number'>寻找重复数(Find the Duplicate Number)</a>
 * <p>给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。</p>
 * <p>假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。</p>
 * <p>你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,3,4,2,2]
 *      输出：2
 *
 * 示例 2：
 *      输入：nums = [3,1,3,4,2]
 *      输出：3
 *     </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= n <= 10^5</li>
 *         <li>nums.length == n + 1</li>
 *         <li>1 <= nums[i] <= n</li>
 *         <li>nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/30 13:49
 */
public class LC0287FindTheDuplicateNumber_M {
    static class Solution {

        /**
         * 循环链表的思路。查找入环点
         */
        public int findDuplicate(int[] nums) {
            int slow = nums[0];
            int fast = nums[nums[0]];
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            slow = 0;
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }

        public int findDuplicate1(int[] nums) {
            for (int idx = 0; idx < nums.length; idx++) {
                // 当前下标所对应的值。如果不等于下标idx+1
                /*
                 * 例如：1,3,4,2,2
                 * ==>置换后变成：
                 * index    0 1 2 3
                 * value    1 2 3 4
                 */
                while (idx + 1 != nums[idx]) {
                    // 目标位置的值等于当前值，出现重复数
                    if (nums[idx] == nums[nums[idx] - 1]) {
                        return nums[idx];
                    }
                    // 将nums[idx]换到下标为：nums[idx]-1的位置
                    swap(nums, idx, nums[idx] - 1);
                }
            }
            return -1;
        }

        private void swap(int[] nums, int i1, int i2) {
            int temp = nums[i1];
            nums[i1] = nums[i2];
            nums[i2] = temp;

        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findDuplicate(new int[]{1, 3, 4, 2, 2}));
        System.out.println(solution.findDuplicate(new int[]{3, 1, 3, 4, 2}));
    }
}